The present invention relates to image segmentation, and more particularly, to graph out image segmentation using a shape prior.
Image segmentation is used to distinguish and partition an object or region (foreground) of a digital image from the background of the digital image. Image segmentation is commonly used, for example, in medical image analysis. Another popular use for image segmentation is in digital photograph editing.
Segmentation is a fundamental task in image processing and numerous methods have been developed to attempt to accurately segment an image. Some image segmentation methods rely on energy minimization in order to partition an image into multiple regions. Such methods include active contour image segmentation methods and graph cut image segmentation methods.
In an active contour method, the energy is typically comprised of image terms, which are regional and/or boundary based, as well as intrinsic regularization terms. An initial contour, or closed curve, is formed on the image, and based on energy minimization, the initial contour iteratively deforms to move to the region or object of interest. Active contour methods, however, can be sensitive to the initialization of the contour, since the energy minimization is subject to local minima. Active contour methods can also be subject to “leaking”, which occurs when due to noise, clutter, poor contrast, etc., the image data does not provide enough information to stop the contour at the desired location.
In a graph cut image segmentation method, an energy minimization is performed on a graph. The graph is typically generated using vertices representing pixels of the image, as well as edges connecting the vertices, often using 4 or 8 neighborhood connectivity. It is also possible that the vertices of the graph could represent the connectivity of pixels in the image, while the edges of the graph represent the edges of the image. The energy in a graph cut image segmentation typically includes a region term that assigns penalties based on labeling a pixel as foreground or background, as well as a boundary term that assigns a penalty based on the dissimilarity of adjacent pixels. Edges connecting the pixels are cut so that each pixel is associated with either the foreground or the background of the image. The energy function to be minimized is typically the summation of weights of the edges that are cut. Conventional graph cut methods are not iterative, and typically achieve global minimization for an energy function. However, in conventional graph cut image segmentation methods, “leaking” can occur when an object has a weak boundary condition or is grouped together with another object having a similar intensity.